public class Solution {
    /*
     * 括号问题
     * i和i-1就是一个括号的问题
     * 状态：F(i) i个括号的组合
     * 状态转移方程：p+q=i-1
     *           F(i) = "(" + p个括号的组合 + ")" + q个括号的组合
     * 返回结果：F(n)
     * 初始状态：F(0) = " "
     * */
    public static List<String> Match(List<List<String>> list, int p, int q) {
        List<String> alist = new ArrayList<>();
        List<String> listP = list.get(p);
        List<String> listQ = list.get(q);
        for (String strP : listP) {
            for (String strQ : listQ) {
                String str = "(" + strP + ")" + strQ;
                alist.add(str);
            }
        }
        return alist;
    }

    public static List<String> generateParenthesis(int n) {
        //可以用数组
        //List<String>[] array = new List[n];
        List<List<String>> list = new ArrayList<>();
        List<String> listchild = new ArrayList<>();
        listchild.add("");
        list.add(listchild);
        for (int i = 1; i <= n; i++) {
            List<String> ablist = new ArrayList<>();
            for (int p = 0; p <= i - 1; p++) {
                int q = i - 1 - p;
                ablist.addAll(Match(list, p, q));
            }
            list.addAll(Collections.singleton(ablist));
        }
        return list.get(n);
    }
}